Data Structures - Programming Assignment 6
The Bag Class with a Binary Search Tree

"Data Structures and Other Objects Using C++" by Michael Main and Walter Savitch, ISBN 0-201-70297-5

1. bintree.h: and bintree.cpp This is the binary tree node template class files.

   NOTE: The functions left() and right() return a reference to the pointer in the node. This is indicated by the & symbol here:

     binary_tree_node*& left( )
   

   The use of a "reference" (indicated by the ampersand) in the return value has two advantages:
   • It now allows a direct assignment such as: p->left() = NULL. This is not a huge advantage since the same thing can be accomplished by using the set_left function.
   • The expression p->left() can be passed as the argument to a function such as: tree_clear(p->left()); The parameter of tree_clear is a reference parameter, so that any changes that tree_clear makes to p->left() will now affect the actual left pointer in the node *p. In this example, the tree_clear function does set its parameter to NULL, so that the total effect of tree_clear(p->left()) is to clear the left subtree of p and to set p's left pointer to NULL.
   In the case of tree_clear, this is not a huge advantage because we could have just set p's left pointer to NULL ourselves. But, in this assignment, there are two functions, bst_remove and bst_remove_max, which are easier to write if we can use p->left() and p->right() as the parameters of recursive calls. See the implementations in bag.cpp for details.
2. bagtest.cpp: A simple interactive test program.
3. bagexam.cpp: A non-interactive test program that will be used to grade the correctness of your bag class.

The Bag Class Using a Binary Search Tree
Discussion of the Assignment

A bag can be defined as a collection that groups elements with no particular positional relationship. A bag allows duplicates. Conceptually it is similar to a physical bag into which elements are placed, e.g., a shopping bag, a school bag for books.

Start by understanding the entire pseudocode for the binary search tree operations . Then read through the portions that I have already implemented for you. Implement the rest of your work in two parts:

(1) The insert and count functions, and

(2) The bst_remove_all and bst_remove_max functions. Don't move to step 2 until you have completely finished and tested step 1.